package com.cheng.learn.leetcode;

/**
 * @description: MxN的格子，算算一共有多少条 路径
 * @author: ChengHaiZhu
 * @create: 2021-03-21 19:28
 **/
public class UniquePaths62 {
    /**
     * 计算有多少条路径从 m+n−2 选 m-1条数据
     * 因为总共会移动 m+n-2次，其中m-1次是下移，n-1次是右移
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {
        long ans = 1;
        for (int x = n, y = 1; y < m; ++x, ++y) {
            ans = ans * x / y;
        }
        return (int) ans;
    }

    /**
     * 计算有多少条路径从 m+n−2 选 n-1条数据
     * 因为总共会移动 m+n-2次，其中m-1次是下移，n-1次是右移
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths2(int m, int n) {
        long ans = 1;
        for (int x = 1, y = m; x < n; ++x, ++y) {
            ans = ans * y / x;
        }
        return (int) ans;
    }

    /**
     * 状态方程，利用上两个点的次数，相加可得 返回下一个点的次数
     * 状态方程： f(i,j)=f(i−1,j)+f(i,j−1) 边界：f(0,j)=1，f(i,0)=1.
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths3(int m, int n) {
        // 这个数组记录当前点的路径个数
        int[][] f = new int[m][n];
        // 赋值边界
        for (int i = 0; i < m; ++i) {
            f[i][0] = 1;
        }
        // 赋值边界
        for (int j = 0; j < n; ++j) {
            f[0][j] = 1;
        }
        // 求非边界点的路径条数
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        // 从第一个点到最后一个点的路径条数就是f[m - 1][n - 1]
        return f[m - 1][n - 1];
    }
}
